The present invention relates to techniques for allocating resources in computer systems.
Computing facilities, such as data centers, often provide a pool of shared resources (for example, CPUs, memory space, bandwidth, storage space, and mobile servers) which can be shared between a number of clients (also referred to as “projects”). For example, assume that a number of projects are using such a facility simultaneously, and that resources can be dynamically reassigned among the projects, but only one project at a time can use a given resource. Also, assume that each project's resource requirements and available resources can be periodically evaluated so that reassignment decisions can be made.
Consider a simplified scenario wherein resources can be migrated instantaneously and at no cost. In this scenario, it is sufficient to migrate resources between projects in response to current (or recently observed) conditions if migration decisions can be initiated instantaneously (as soon as any load imbalance is observed) and if these decisions can be made infinitely often.
However, if the re-evaluations of system conditions are infrequent enough that a non-negligible amount of work can be done between the re-evaluation points, then a forward-looking resource re-assignment policy is preferable. That is, resources should ideally be migrated from project i to project/only if the expected utility gain of project j during the next time interval outweighs the expected utility loss of project i during that interval.
Now consider a more-realistic scenario when resource migrations require a non-negligible time during which resources are idling (or are not fully utilized) or if there is some cost associated with resource migrations. In this case, resources should be migrated from project i to project j only if the expected long-term utility gain of project j outweighs the expected long-term utility loss of project i. That is, a poor resource allocation decision might require another reassignment at the very next decision point, thereby incurring another re-assignment cost. Also, the backlog of waiting jobs can significantly increase during the time interval when a poor resource allocation decision was made, and it might take many time steps to reduce this backlog.
Hence, when making resource allocation decisions, the system designer should consider not only the immediate benefit they will bring to the system during the next time interval, but also the long-term effects in terms of future migration costs and demand-resource match.
Note that a solution to the above problem can address many important problems, such as migrating CPUs or memory pages between resource pools, migrating servers among projects in a data center, reassigning I/O bandwidth among processes running on a processor module (or between sessions in an ATM, wireless, or TCP/IP network using end-to-end congestion control), and dynamically re-assigning memory space or disk space.